package 树.红黑树;

import 树.AVL树.AVL;

public class RBTree {
    //用boolean值代表红黑
    private static final boolean red = false;
    private static final boolean black = true;
    class RBNode {
        RBNode left;
        RBNode right;
        RBNode parent;
        int val;
        boolean color;

        public RBNode(RBNode left, RBNode right, RBNode parent , int val, boolean color) {
            this.left = left;
            this.right = right;
            this.val = val;
            this.color = color;
        }

        public RBNode(int val, boolean color) {
            this.val = val;
            this.color = color;
        }
    }
    RBNode root ;
    public void insert(int val){
        RBNode rbVal = new RBNode(val , black);
        root = insert(root , rbVal);
    }

    private RBNode insert(RBNode root, RBNode avl) {
        if (root == null){
            root = avl;
        }else {
            if (root.val > avl.val){
                root.left = insert(root.left , avl);
                avl.color = red;
                avl.parent = root;
                insertFixUp(avl);
            }else if (root.val < avl.val){
                root.right = insert(root.right , avl);
                avl.color = red;
                avl.parent = root;
                insertFixUp(avl);
            }else {
                System.out.println("已经有这个值了不要重复添加");
            }
        }
        return root;
    }

    private void insertFixUp(RBNode avl) {
        //千万不要这么写哦，如果吧父亲和爷爷节点定义在前面，那怎么循环呢？
        // RBNode parent  = avl.parent, grandParent = parent.parent;
        RBNode parent , grandParent;
        while ((parent = avl.parent) != null && parent.color == red){
            grandParent = parent.parent;
            if (parent == grandParent.left){
                RBNode uncle = grandParent.right;
                if (uncle != null && uncle.color == red){
                    parent.color = black;
                    uncle.color = black;
                    grandParent.color = red;
                    avl = grandParent;
                    continue;//记得要冲这里跳出到下一个执行哦
                }
                if (avl == parent.right){
                    //跟AVL左旋操作如出一辙
                    turnLeft(parent);
                    RBNode cur = parent;
                    parent = avl;
                    avl = cur;
                }
                parent.color = black;
                grandParent.color = red;
                turnRight(grandParent);
            }else {
                //父节点是当前爷爷节点的右子树
                RBNode uncle = grandParent.left;
                if (uncle != null && uncle.color == red){
                    parent.color = black;
                    uncle.color = black;
                    grandParent.color = red;
                    avl = grandParent;
                    continue;
                }
                if (avl == parent.left){
                    turnRight(parent);
                    RBNode cur = parent;
                    parent = avl;
                    avl = cur;
                }
                parent.color = black;
                grandParent.color = red;
                turnLeft(grandParent);
            }
        }
        //不管怎么样，操作完之后跟节点有可能不黑，我们给他涂黑就好了
        root.color = black;
    }

    private void turnRight(RBNode avl) {
        RBNode cur = avl.left;
        avl.left = cur.right;
        if (cur.right != null){
            cur.right.parent = avl;
        }
        cur.parent = avl.parent;
        if (avl.parent == null){
            root = cur;
        }
        if (avl.parent.left == avl){
            avl.parent.left = cur;
        }else {
            avl.parent.right = cur;
        }
        cur.right = avl;
        avl.parent = cur;
    }

    private void turnLeft(RBNode avl) {
        RBNode cur = avl.right;
        avl.right = cur.left;
        if (cur.left != null){
            cur.left.parent = avl;
        }
        cur.parent = avl.parent;
        //当然有可能原本的父节点是根没有爷爷节点，所以交换后，此时的节点即（avl.right）变成头节点
        if (avl.parent == null){
            root = cur;
        }
        if (avl.parent.left == avl){
            avl.parent.left = cur;
        }else {
            avl.parent.right = cur;
        }
        cur.left = avl;
        avl.parent = cur;
    }

    public void find(int val){
        find(root , val);
    }
    private RBNode find(RBNode avl , int val){
        if (avl == null){
            return null;
        }
        if (avl.val > val){
            return find(avl.left , val);
        }else if (avl.val < val){
            return find(avl.right , val);
        }else {
            return root;
        }
    }

    public void delete(int val){
        RBNode avl = find(root , val);
        if (avl != null){
            delete(avl);
        }else {
            System.out.println("节点不存在，删个毛线");
        }
    }

    private void delete(RBNode avl){
        if (avl.left != null && avl.right != null){
            deleteDoubleChild(avl);
        }
        if (avl.left == null && avl.right == null){
            deleteNoChild(avl);
        }
        if (avl.left != null){
            deleteLeftChild(avl);
        }
        if (avl.right != null){
            deleteRightChild(avl);
        }
    }

    private void deleteRightChild(RBNode avl) {
        RBNode child = avl.right;
        RBNode parent = avl.parent;
        boolean color = avl.color;
        if (avl.parent != null){
            if (parent.left == avl){
                parent.left = child;
                child.parent = parent;
            }else {
                parent.right = child;
                child.parent = parent;
            }
        }else {
            root = avl.right;
        }
        if (color == black){
            deleteFixUp(child , parent);
        }
        return;
    }

    private void deleteLeftChild(RBNode avl) {
        RBNode child = avl.left;
        RBNode parent = avl.parent;
        boolean color = avl.color;
        if (avl.parent != null){
            if (parent.left == avl){
                parent.left = child;
                child.parent = parent;
            }else {
                parent.right = child;
                child.parent = parent;
            }
        }else {
            root = avl.left;
        }
        if (color == black){
            deleteFixUp(child , parent);
        }
        return;

    }

    private void deleteNoChild(RBNode avl) {
        RBNode child = null;
        RBNode parent = avl.parent;
        boolean color = avl.color;
        if (avl.parent != null){
            if (avl.parent.left == avl){
                avl.parent.left = null;
            }else {
                avl.parent.right = null;
            }
        }else {
            root = null;
        }
        if (avl.color == black){
            //红节点不用管，删了不影响RBTree只有删黑点的时候要修正
            deleteFixUp(child , parent);
        }
        return;
    }

    private void deleteDoubleChild(RBNode avl) {
        //找到右子树的最大即后继节点
        RBNode rep = min(avl.right);
        avl.val = rep.val;
        delete(rep);
        return;
    }
    private void deleteFixUp(RBNode avl , RBNode parent) {
        RBNode brother;
        while ((avl == null || avl.color == black) && avl != root){
            if (avl == parent.left){
                brother = parent.right;
                if (brother.color == red){
                    brother.color = black;
                    parent.color = red;
                    turnLeft(parent);
                    brother = parent.right;
                }
                //这步走完兄弟肯定黑
                if ((brother.left == null || brother.left.color == black) && (brother.right == null || brother.right.color == black)){
                    brother.color = red;
                    avl = parent;
                    parent = parent.parent;
                }else {
                    if (brother.right.color == black){
                        //说明左树是红的
                        brother.left.color = black;
                        brother.color = red;
                        turnRight(brother);
                        brother = parent.right;
                    }
                    //截止这里他兄弟右树肯定红了，我怎么知道？你猜上一步旋转是为了什么
                    brother.color = parent.color;
                    parent.color = black;
                    brother.right.color = black;
                    turnLeft(parent);
                    avl = root;//其实下一圈循环也就跳出了
                    break;
                }
            }else {
                brother = parent.left;
                if (brother.color == red){
                    brother.color = black;
                    parent.color = red;
                    turnRight(parent);
                    brother = parent.left;
                }
                if ((brother.left == null || brother.left.color == black) && (brother.right == null || brother.right.color == black)){
                    brother.color = red;
                    avl = parent;
                    parent = parent.parent;
                }else {
                    if (brother.left.color == black){
                        brother.right.color = black;
                        brother.color = red;
                        turnLeft(brother);
                        brother = parent.left;
                    }
                    brother.color = parent.color;
                    parent.color = black;
                    brother.left.color = black;
                    turnRight(parent);
                    avl = root;
                    break;
                }
            }
            //到现在avl肯定是树根我们把他不管怎样涂黑
            if (avl != null){
                avl.color = black;
            }
        }
    }
    private RBNode min(RBNode root){
        if (root.left == null){
            return root;
        }
        return min(root.left);
    }
    private RBNode max(RBNode root){
        if (root.right == null){
            return root;
        }
        return max(root.right);
    }
}
